package chunzhao.Jun_20;

/**
 * @Classname Top1W
 * @Description TODO
 * @Date 2024/1/20 16:15
 * @Created by ZHL17
 */
//  归并排序
public class Merge {
    public static void main(String[] args) {
        int[] arr = {1,25,14,19,56,45,34,41,87,9};
        mergeSort(arr,0,arr.length - 1);
        for (int i : arr) {
            System.out.print(i + " ");
        }

    }
    public static void mergeSort(int[] nums, int left, int right) {
        if (left >= right) return ;
        int l = left;
        int r = right;
        int mid = l + ((r - l) >> 1);
        mergeSort(nums,l,mid);
        mergeSort(nums,mid + 1, r);
        merge(nums,l,mid,r);

    }
    public static void merge(int[] nums, int left, int mid, int right) {
        if (left >= right) return ;
        int[] help = new int[right - left + 1];
        int l = left;
        int rl = mid + 1;
        int i = 0;
        while (l <= mid && rl <= right) {
            if (nums[l] < nums[rl]) {
                help[i++] = nums[l];
                l++;
            } else {
                help[i++] = nums[rl];
                rl++;
            }
        }
        while (l <= mid) {
            help[i++] = nums[l];
            l++;
        }
        while (rl <= right) {
            help[i++] = nums[rl];
            rl++;
        }
        i = 0;
        for (int j = left; j <= right; j++) {
            nums[j] = help[i++];
        }
    }
}
